#include <stdio.h>
#include <stdlib.h>
#include "DynamicArray.h"

bool InsertArrayTail(DArray *a,ElementType element);
bool RemoveByIndex(DArray *a,int index,void (*ClearPtr)(ElementType));
bool RemoveByElement(DArray *a, ElementType element, bool (*funcPtr)(ElementType, ElementType),void (*ClearPtr)(ElementType));
DArray FindElement(DArray *a, void *element,bool (*funcPtr)(ElementType,ElementType));
void DisplayDynamicArray(DArray * a,void (*funcPtr)(ElementType));
void Sort(DArray *a,bool (*funcPtr)(ElementType,ElementType));
void ClearDArray(DArray *a, void (*funcPtr)(ElementType));

void InitDynamicArray(DArray *a)
{
    a->dp = NULL;
    a->len = 0;
    a->size = 0;

    a->InsertArrayTail = InsertArrayTail;
    a->RemoveByElement = RemoveByElement;
    a->FindElement = FindElement;
    a->DisplayDynamicArray = DisplayDynamicArray;
    a->Sort = Sort;
    a->ClearDArray = ClearDArray;
}

bool InsertArrayTail(DArray *a, ElementType element)
{
    if(a->dp == NULL)
    {
        a->size = (a->size+1) * 2;
        a->dp = (ElementType *)malloc(a->size * sizeof(ElementType));
        if(a->dp == NULL)
        {
            InitDynamicArray(a);
            return false;
        }
    }
    else if(a->len >= a->size)
    {
        int newSize = (a->size + 1) * 2;
        ElementType * newDp = realloc(a->dp,sizeof(ElementType) * newSize);
        if(newDp == NULL)
        {
            return false;
        }    
        a->dp = newDp;
        a->size = newSize;
    }

    a->dp[a->len++] = element;
    return true;
}

bool RemoveByIndex(DArray *a,int index,void (*ClearPtr)(ElementType))
{
    if(index < 0 || index >= a->len)
    {
        printf("删除的是非法位置！\n");
        return false;
    }
    if(ClearPtr != NULL)
    {
        ClearPtr(a->dp[index]);
    }
    for(int i = index ; i < a->len - 1; i++)
    {
        a->dp[i] = a->dp[i+1];
    }
    a->len--;
    return true;
}

bool RemoveByElement(DArray *a, ElementType element,bool (*funcPtr)(ElementType,ElementType),void (*ClearPtr)(ElementType))
{
    for(int i = 0; i < a->len; i++)
    {
        if(funcPtr(element,a->dp[i]) == true)
        {
            if(RemoveByIndex(a,i,ClearPtr) == false)
            {
                return false;
            }
            i--;
        }
    }
    return true;
}

DArray  FindElement(DArray *a, void *element, bool (*funcPtr)(ElementType, ElementType))
{
    DArray result;
    InitDynamicArray(&result);
    for(int i = 0; i < a->len; i++)
    {
        if(funcPtr(element,a->dp[i]) == true)
        InsertArrayTail(&result,a->dp[i]);
    }
    return result;
}

//输出动态数组
void DisplayDynamicArray(DArray *a,void (*funcPtr)(ElementType))
{
    for(int i = 0; i < a->len; i++)
    {
        funcPtr(a->dp[i]);
    }
}

void FastSort(ElementType *s,int start,int end,bool (*funcptr)(ElementType, ElementType ))
{
    if(start >= end)
        return;
  
    int left = start;
    int right = end;
    ElementType temp = s[left];
    while(left < right)
    {
        while(left < right && funcptr(s[right],temp) == true)
        {
            right--;
        }
        if(left < right)
        {
            s[left] = s[right];
            left++;
        }
        while(left < right && funcptr(s[left],temp) == false)
        {
            left++;
        }
        if(left < right)
        {
            s[right] = s[left];
            right--;
        }
        s[left] = temp;
    }
    FastSort(s,start,left-1,funcptr);
    FastSort(s,right+1,end,funcptr);
}

void Sort(DArray *a, bool (*funcPtr)(ElementType, ElementType))
{
    FastSort(a->dp,0,a->len-1,funcPtr);
}

void ClearDArray(DArray *a, void (*funcPtr)(ElementType))
{
    if(funcPtr != NULL)
    for(int i = 0; i < a->len; i++)
    {
        funcPtr(a->dp[i]);
    }
    free(a->dp);
    InitDynamicArray(a);
}
